By the end of this lecture, you will be able to achieve the following learning objectives:
- Define what a path is, including its components (vertices, edges) and how its cost is calculated.
- Distinguish between the two main problems: shortest paths in weighted graphs and ordering in dependency graphs.
- Explain the intuition and step-by-step process of Dijkstra’s Algorithm.
- Understand the purpose and mechanism of Topological Sort for Directed Acyclic Graphs (DAGs).
- Apply both of these algorithms to small graph examples manually.
Today's Algorithms
1# 1. Dijkstra's Algorithm
2Goal: For finding the lowest cost path (e.g., fastest route).
3
4# 2. Topological Sort
5Goal: For finding a valid sequence (e.g., task order).